package com.zzh.dac;
/*
 *汉诺塔问题：
 *  1.如果只有一个盘，A->C
 * 如果我们有n>=2情况，我们总是可以看做是两个盘1.最下边的盘2.上面的盘
 * 1)先把最上面的盘A->B
 * 2)最下边的盘A->C
 * 3)把B塔的所有盘从B->C
 * */
public class HanoiTower {
    private static int cnt=0;
    public static void main(String[] args) {
        hanoiTower(5,'A','B','C');
        System.out.println(cnt);
    }
    //汉诺塔的移动方法
    //使用分治算法
    public static void hanoiTower(int num,char a,char b,char c){
        /*以下为具体算法*/
        //如果只有一个盘
        cnt++;
        if (num==1){
            System.out.printf("第1个盘子 %c->%c\n",a,c);
        }else{
            //如果我们有n>=2情况，我们总是可以看做是两个盘1.最下边的一个盘2.上面的所有盘
            //1.先把最上面的所有盘A->B，移动过程会使用C
            hanoiTower(num-1,a,c,b);
            //2.把最下边的盘A->C
            System.out.printf("第%d个盘子 %c->%c\n",num,a,c);
            //3.把B塔的所有盘从B->C，移动过程使用到A塔
            hanoiTower(num-1,b,a,c);
        }


    }
}
